The present invention relates to digital computer systems, and in particular computer operating systems which support multiple simultaneous tasks.
A modem computer system typically comprises a central processing unit (CPU), and other supporting hardware such as system memory, communications busses, input/output controllers, storage devices, etc. The CPU is the heart of the system. It executes the instructions which comprise a computer program and directs the operation of the other system components. Typically, the instructions which execute on the CPU may be part of the computer""s operating system, or may be part of an application program which performs some particular work for a user.
The operating system may be thought of as that part of the programming code executing on the computer, which regulates the computer""s function, while the application programs perform specific work on behalf of a user. Operating systems vary considerably in complexity and function. A very simple operating system for a single-user computer may handle only a single task at a time, mapping all data into a single address space, and swapping data into and out of the address space whenever a new task must be performed. An operating system for a computer which supports multiple simultaneous users must manage the allocation of system resources among the different users. In particular, it must manage the allocation of address space and system memory.
The address space of the system is the range of addresses available to reference data, instructions, etc., and is determined by the size (bit length) of the address. Usually, the address space is significantly larger than the number of actual physical memory locations available on the system. The address size is one of the fundamental architectural features of the computer system. All other things being equal, a larger address size is naturally desirable from the standpoint of capacity of the system to do work. However, the address size entails significant hardware cost. The size of buses, registers, and logic units throughout the system is intimately tied to the address size.
In the early days of computers, hardware was a relatively expensive commodity. Many early systems used 16-bit or smaller addresses. Usually, the amount of data contained in these systems exceeded the size of the address space. An individual program might fit well within the address space, but a user might have many programs to execute on the system. Additionally, multi-user systems required space for each user.
The earliest systems executed only a single application at a time. Typically, storage became hierarchical. Although the total number of addresses exceeded the address space available in main memory, address space could be re-used. Data (including programs) were normally stored in a large secondary storage on disk, drum, tape or other secondary storage devices. When a particular application was needed, it was loaded into main memory and addresses were mapped into the address space of main memory. When no longer needed, it was deleted from main memory but retained in secondary storage. The address space was then re-used. If the same application was needed again, it could be loaded again into main memory.
As computers became more sophisticated, it became common for computer systems to execute multiple tasks concurrently. Operating systems designed for such computer systems were required to manage operations within the available address space of the computer. Since the addresses needed typically exceeded the address space available in the processor""s hardware, this was done by allocating a separate address space to each task, resulting in multiple virtual address spaces. Typically, the task""s virtual address space was the same size as the address space of the computer""s processor.
This multiple virtual address space approach necessarily meant that different bytes of data might have the same virtual address, although they would be in the virtual address spaces of different tasks. When a task was loaded into main memory from secondary storage, a mapping mechanism mapped virtual addresses in the virtual address space of the task to physical addresses in the main memory of the computer system. This increased the complexity of the operating system, but was necessary to cope with the limited size of the system""s address space.
As an alternative to the multiple virtual address space architecture, it possible to utilize a single very large system address space, one which is sufficiently large that it is not necessary to have multiple overlapping virtual address spaces, one for each task. Each task has its own discrete portion of the large system address space. One major impediment to this alternative architecture is that is requires a very large system address space, and consequently requires additional hardware to support it. When hardware was very expensive, this alternative appeared unattractive. For that reason, most multi-tasking systems have utilized the multiple virtual address space approach.
With the alternative single large address space approach, programs and other data stored in a computer system can be assigned persistent, unique logical addresses in the large system address space. Because these logical addresses are not duplicated, they can be used to identify data either in main memory or in secondary memory. For this reason, this alternative is sometimes referred to as a single level storage architecture. Examples of such an alternative architecture are the IBM System/38 computer system (formerly manufactured and distributed by IBM Corporation), its successor, the IBM AS/400 System (currently manufactured and distributed by IBM Corporation), and the Opal system at the University of Washington. For additional background concerning the IBM System/38 and IBM AS/400 System, see IBM System/38 Technical Developments (International Business Machines Corporation, 1978), IBM Application System/400 Technology (International Business Machines Corporation, 1988), and IBM Application System/400 Technology Journal, Version 2 (International Business Machines Corporation, 1992). The Opal system is described in a series of academic papers, including J. Chase, et al., xe2x80x9cOpal: A Single Address Space System for 64-bit Architecturesxe2x80x9d, Proc. IEEE Workshop on Workstation Operating Systems (April, 1992).
When compared with the more traditional multiple virtual address space approach, the single level storage architecture offers certain advantages. These advantages are particularly applicable to object oriented programming applications. The object oriented (OO) programming paradigm anticipates that a large number of small code segments will have internal references (pointers) to one another, that these segments may be owned by different users, that during execution of a task, flow of control may jump frequently from one segment to another, and that different tasks executing on behalf of different users will often execute the same code segment.
Where a system uses multiple virtual address spaces, the pointers to different code segments will reference code in the virtual address space of another task or user. Resolution of these pointers becomes difficult. Because multiple overlapping virtual address spaces exist, it is possible that different code segments will share the same virtual address, but in the address space of different tasks or users. It is also possible that the executing task will have assigned the virtual address to some other data. Therefore, it is not possible to directly reference data or code in a segment belonging to a different task or user in the same manner an executing task would use a pointer to its own code in its own virtual address space. There must be a mechanism for resolving the various pointers so that the correct code segment is referenced.
Such mechanisms for resolving pointers in a multiple virtual address space system are possible, but they are awkward and tend to impose a burden on system performance. On the other hand, a single level store architecture can cope with such pointers more easily. Because each code or other data segment will have its own logical address in the single large system address space, there is no need for a mapping mechanism when referencing another code or data segment, even where that code or data is controlled by another task or user. It may be necessary to have a mechanism for verifying access rights, but the pointer addresses themselves do not need to be re-mapped for each new task. This is a substantial advantage where many pointers are used to point to code or other data segments of different tasks or users, and task execution can flow unpredictably from one to another.
Recently, there has been a significant interest in the object-oriented (OO) programming paradigm. The number of OO applications available is rapidly mushrooming. Object-oriented applications are not the only ones which may have pointers referencing code or other data controlled by different users. But OO application rely heavily on these types of operations. As object-oriented applications become more common, the burden of resolving pointers in a multiple virtual address space environment increases.
Another development in the evolution of the computer industry has been the relative decline in hardware costs. Historically, the size of addresses has grown as hardware costs have declined. The earlier 16-bit address based systems have largely been supplanted by 32-bit system. More recently, several commodity processors have been introduced having 64-bit address capability.
Unlike the earlier increases in address size, the increase in size to 64 bits has a revolutionary potential. Even where every task has its own range of addresses and every new piece of data is assigned a persistent address which is not re-used, it is unlikely that all the addresses in a 64-bit address space will be consumed in the lifetime of a given computer system. Thus, a 64-bit address is large enough to support a single level storage architecture. Moreover, it is a capability which is available to the system designer at no cost. Commodity processors simply offer this enormous range of addresses, whether the system designer uses them or not. At the present time, few systems have taken advantage of the full range of 64-bit address space.
The increasing use of OO applications, as well as the availability of large addresses on modem processor hardware, provide some justification for a single level storage architecture. However, architectural decisions for computer systems are not made in a vacuum. There is a long history of computer system development using the multiple virtual address space model. Any computer system architecture has its own characteristic advantages and disadvantages. Operating systems have been designed, and application software written, to take advantage of multiple virtual address spaces. Given the existing investment in these designs, it is difficult for many systems designers and users to change to a single level store architecture, despite any theoretical advantage that may be available.
It would be desirable to obtain the benefits of a single level store architecture computer system, particularly in systems which execute a significant number of OO applications. However, it is very difficult to change something so fundamental as the addressing model used in a computer system. Altering a conventional multi-tasking, multiple virtual address space system, to conform to a single level store design would typically require massive re-writing of the operating system and the application software.
It is therefore an object of the present invention to provide an enhanced computer system architecture.
Another object of this invention is to increase the performance of a computer system.
Another object of this invention is to enhance the ability of a computer system to execute multiple concurrent tasks.
Another object of this invention is to enhance the ability of a computer system to share data and code between multiple concurrent tasks.
Another object of this invention is to enhance the ability of a computer system to execute tasks involving object-oriented programming applications.
Another object of this invention is to reduce the complexity of pointer resolution among different tasks in a multi-tasking computer system.
Another object of this invention is to enhance the ability of a multi-tasking computer system having multiple virtual address spaces to provide functional advantages of a single address space computer system.
A multi-tasking operating system of a computer system allocates a respective virtual address space to each task, the virtual address spaces for the different tasks overlapping. For at least some tasks, a portion of virtual address space is reserved as a shared address space (SAS) region. These tasks are said to be xe2x80x9cparticipatingxe2x80x9d in the SAS region. The SAS region occupies the same range of virtual addresses in the virtual address space of each participating task. Certain classes of data intended for sharing among multiple tasks are assigned addresses in the range of the shared address space region. Assignments of such addresses in the shared address space region are unique and persistent. In this manner, it is possible for a multi-tasking multiple virtual address space computer system to behave like a single level store computer system when performing certain tasks.
In the preferred embodiment, certain facilities are added to the base operating system of a conventional multi-tasking computer system to support the SAS region and associated function. These facilities are collectively referred to as the xe2x80x9cSAS Serverxe2x80x9d. The three chief facilities are a join facility, an attach facility, and an external paging facility.
The join facility permits a task to xe2x80x9cjoinxe2x80x9d (xe2x80x9cparticipatexe2x80x9d in) the SAS region, i.e., to take advantage of the single level storage characteristics of the SAS region. It is preferred that each task can join the SAS region individually, so that tasks are not required to join. By allowing a task to not participate in the SAS region, the operating system retains full compatibility with applications that may use portions of the SAS region for application specific purposes. A task joins a region by issuing a specific command to invoke the join facility. The SAS server maintains a record of tasks which are participating in the SAS region.
The attach facility is used by a participating task to attach blocks of memory within the SAS region. The SAS region is logically partitioned into blocks, which are the basic unit of access control. After joining the SAS region, a task can create blocks in the SAS region or attach blocks in the SAS region created by other tasks. The attach facility may either be invoked explicitly by a command to attach blocks, or implicitly by a memory reference to a location within a block which has not yet been attached. The SAS server maintains a record of attached blocks for each individual task. The fact that a task has joined the SAS region does not automatically grant it authority to access any particular block within the region. The attach facility is therefore responsible for verifying the authority of the task to access the requested block, and updating the record of attached blocks if an explicit or implicit request to access a block is successful. The SAS server also maintains a record of all persistent allocated blocks. This record enables the facility to allocate new blocks in unused address ranges, and guarantee that objects within the SAS region are loaded to consistent virtual addresses.
The external pager (called xe2x80x9cexternalxe2x80x9d because in the preferred embodiment it is external to the base operating system) manages paging within the SAS region. In the base operating system, when an executing task references a memory location, the system checks to determine whether the referenced page is currently loaded in physical memory. If not, an exception is generated by the operating system. A system default memory pager is called to bring the requested page in from storage.
This normal procedure is modified if the memory reference is within the SAS region. In that case, the exception causes the external pager to be called. The pager looks for the block in the executing task""s record of attached blocks (which indicates authority to access the block containing the requested page). If the block entry is found (the block has been attached), the requested page is added to the task""s page table. If necessary, the page is also loaded from storage and placed in memory (note that the page may already be in physical memory if it is used by another task). Subsequent attempts by the same task to access the same page will find it in the task""s page table, so that no exception will be generated and the memory location will be accessed directly.
The above described system is a hybrid, which is neither purely a multiple address space system nor a single level store system. Because it builds upon a multiple virtual address space system, it is compatible with many existing architectures, and may execute programs written for these architectures with little or no modification. At the same time, it provides many of the advantages of single level store, e.g., improved ability to resolve pointers among different tasks and execute object-oriented applications where objects are controlled by different users.